package com.yun.algorithmproblem.leetcodenotcomplete;

/**
 * 3086. 拾起 K 个 1 需要的最少行动次数
 * <p>
 * 给你一个下标从 0 开始的二进制数组 nums，其长度为 n ；另给你一个 正整数 k 以及一个 非负整数 maxChanges 。
 * <p>
 * Alice 在玩一个游戏，游戏的目标是让 Alice 使用 最少 数量的 行动 次数从 nums 中拾起 k 个 1 。
 * 游戏开始时，Alice 可以选择数组 [0, n - 1] 范围内的任何索引 aliceIndex 站立。如果 nums[aliceIndex] == 1 ，Alice 会拾起一个 1 ，并且 nums[aliceIndex] 变成0（这 不算 作一次行动）。
 * 之后，Alice 可以执行 任意数量 的 行动（包括零次），在每次行动中 Alice 必须 恰好 执行以下动作之一：
 * 选择任意一个下标 j != aliceIndex 且满足 nums[j] == 0 ，然后将 nums[j] 设置为 1 。这个动作最多可以执行 maxChanges 次。
 * 选择任意两个相邻的下标 x 和 y（|x - y| == 1）且满足 nums[x] == 1, nums[y] == 0 ，然后交换它们的值（将 nums[y] = 1 和 nums[x] = 0）。如果 y == aliceIndex，在这次行动后 Alice 拾起一个 1 ，并且 nums[y] 变成 0 。
 * 返回 Alice 拾起 恰好 k 个 1 所需的 最少 行动次数。
 */
public class Leetcode3086 {

    public static void main(String[] args) {
        int[] nums = {1, 1};
        int k = 1;
        int maxChanges = 2;
        Leetcode3086 obj = new Leetcode3086();
        System.out.println(obj.minimumMoves(nums, k, maxChanges));
    }


    public long minimumMoves(int[] nums, int k, int maxChanges) {
        long min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            long step = step(nums, k, maxChanges, i);
            if (step == 0) {
                return 0;
            } else {
                if (step < min) {
                    min = step;
                }
            }
        }
        return min;
    }

    private long step(int[] nums, int k, int maxChanges, int i) {
        int n = nums.length;
        long countOne = 0;
        if (nums[i] == 1) {
            countOne++;
            if (countOne == k) {
                return 0;
            }
        }
        long step = 0;
        if (0 <= (i - 1) && nums[i - 1] == 1) {
            step++;
            countOne++;
            if (countOne == k) {
                return step;
            }
        }
        if ((i + 1) < n && nums[i + 1] == 1) {
            step++;
            countOne++;
            if (countOne == k) {
                return step;
            }
        }
        if ((k - countOne) <= maxChanges) {
            return step + (k - countOne) * 2L;
        } else {
            step = step + maxChanges * 2L;
            countOne += maxChanges;
            int left = i - 2;
            int right = i + 2;
            while (countOne < k ) {
                if (0 <= left && nums[left] == 1) {
                    step += i - left;
                    countOne++;
                    if (countOne == k) {
                        return step;
                    }
                }
                left--;
                if (right < n && nums[right] == 1) {
                    step += right - i;
                    countOne++;
                    if (countOne == k) {
                        return step;
                    }
                }
                right++;
            }
        }
        return Integer.MIN_VALUE;
    }

}
